The use of so-called “turbo codes” in decoders of communication systems was first proposed by C. Berru et al. in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes,” ICC'93, Geneva, Switzerland, pp. 1064–1070, May 1993, the disclosure of which is incorporated by reference herein. Since then, the error correcting capabilities of turbo codes have been of significant interest in communication system design.
In general, the decoding of turbo codes is performed by using soft input/soft output (SISO) decoders. SISO decoders provide a real number that serves as a measure of the probability of a correct decision on a received bit. The probability measures are iteratively improved. The SISO decoder proposed by C. Berru et al. incorporates a modified maximum a posteriori (MAP) decoding algorithm, also known as the Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm, which was first proposed in L. Bahl et al., “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, Vol. IT-20, pp. 284–287, March 1974, the disclosure of which is incorporated by reference herein. A decoding technique that bears resemblance to the BCJR algorithm had been proposed by Gallager in his work on low density parity check codes, see, e.g., R. G. Gallager, “Low Density Parity Check Codes,” IRE Trans. Inform. Theory, Vol. IT-8, pp. 31–38, January 1962, the disclosure of which is incorporated by reference herein.
The MAP algorithm evaluates the most likely information bit that might have been transmitted in a coded sequence. In contrast, the Viterbi algorithm determines the most likely code word that might have been transmitted. It is well known that MAP decoders outperform Viterbi decoders at low signal-to-noise ratios and high bit error rates. Owing to design economy considerations, a direct implementation of the original MAP algorithm in hardware is not favored.
However, simplifications of the MAP algorithm render feasible VLSI (very large scale integration) implementations. Known simplifications of the MAP algorithm include the “log-MAP” algorithm, the “max-log-MAP” algorithm and the “max*-log-MAP” algorithm. In the logarithmic domain, otherwise expensive multiplications and divisions are transformed to more inexpensive addition/subtraction operations. For example, in turbo decoders, add-compare-select-add operations are typically employed for evaluating state metrics used in determining the measure of probability of a correct decision on a received bit.
However, existing add-compare-select-add operations, as well as other arithmetic operations, are generally sequential in nature, which can lead to significant processing bottlenecks in the turbo decoders.
Thus, in turbo decoders, there is a need for techniques which improve arithmetic operation performance, which overcome the existing drawbacks inherent in a sequential handling of such operations.